package com.leetCode.four;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Set;

public class Problem42 {

	public static void main(String[] args) throws Exception {
		 Solution s = getInstance();
		 
		 int[] test = {2,0,2};
		 int[] test2 = new int[5000];
		 for (int i = 0; i < test2.length; i++) {
			 test2[i] = (int) (Math.random()*100000);
		}
		 System.out.println("的mo");
//		 int[] test = {4,2,3};
		 int trap = s.trap(test2);
		 
		 
		 System.out.println(trap);
//{3=[7], 2=[3, 8, 10], 1=[1, 4, 6, 9, 11], 0=[0, 2, 5]}

	}
	
	class Solution {
	    public int trap(int[] height) {
	    	java.util.Hashtable<Integer, Integer[]> ht = new java.util.Hashtable<>();
	    	int max = -1;
	    	long currentTimeMillis = System.currentTimeMillis();
	        for (int i=0,length=height.length; i<length; i++) {
	        	int nowValue = height[i];
	        	max = nowValue>max?nowValue:max;
	        	for (int j = 1; j <= nowValue; j++) {
		        	if(!ht.containsKey(j)){
		        		ht.put(j, new Integer[2]);
		        	}
		        	Integer[] list= ht.get(j);
					if(list[0] == null){
						list[0] = i;
					}else{
						list[1] = i;
					}
				}
	        	if(!ht.containsKey(nowValue)){
	        		ht.put(nowValue, new Integer[2]);
	        	}
	        	Integer[] list= ht.get(nowValue);
				if(list[0] == null){
					list[0] = i;
				}else{
					list[1] = i;
				}
			}
	        //从最上面开始,往下分布
//	        for(int i=max; i>1; i--){
//	        	for (int j = i-1; j >= 1; j--) {
//		        	if(ht.containsKey(j)){
//		        		Integer[] hti = ht.get(i);
//		        		Integer[] htj = ht.get(j);
//		        		if(hti[0]<htj[0]){
//		        			htj[0] = hti[0];
//		        		}else if(hti[1]!=null && ( htj[1]==null ||hti[1]>htj[1] )){
//		        			htj[1] = hti[1];
//		        		}
//		        		
//		        	}else{
//		        		ht.put(j, ht.get(i));
//		        	}
//				}
//	        }
	        System.out.println("第一个用时:"+(System.currentTimeMillis()-currentTimeMillis));
	        currentTimeMillis = System.currentTimeMillis();
	    	int result = 0;
	    	Set<java.util.Map.Entry<Integer, Integer[]>> entrySet = ht.entrySet();
	    	for (java.util.Map.Entry<Integer, Integer[]> entry : entrySet) {
	    		Integer key = entry.getKey();
	    		Integer[] value = entry.getValue();
//	    		System.out.println(key+":"+Arrays.toString(value));
	    		if(value[1]!=null){
	    			for (int i = value[0]+1; i < value[1]; i++) {
						if(height[i]<key){//从左往右开始,如果遇到值比本身低的,说明雨水可以填充
							result++;
						}
					}
	    		}
			}
	    	 System.out.println("第一个用时:"+(System.currentTimeMillis()-currentTimeMillis));
	    	return result;
	    }
	}
	
	static Solution getInstance() throws Exception{
		String className = Thread.currentThread().getStackTrace()[1].getClassName();
		Class<?> forName = Class.forName(className);
		Method method = forName.getMethod("newS", null);
		Solution solution = (Solution) method.invoke(forName.newInstance(),null);
		return solution;
	}
	
	public Solution newS(){
		return new Solution();
	}
	
}
